import java.util.*;

public class Solution {
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i],map.getOrDefault(words[i],0) + 1);
        }


        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
             if (minHeap.size() < k) {
                 minHeap.offer(entry);
             } else {
                 if (entry.getValue().compareTo(minHeap.peek().getValue()) > 0) {
                      minHeap.poll();
                      minHeap.offer(entry);
                 } else {
                     if (entry.getValue().compareTo(minHeap.peek().getValue()) == 0) {
                         if (entry.getKey().compareTo(minHeap.peek().getKey()) < 0) {
                             minHeap.poll();
                             minHeap.offer(entry);
                         }
                     }
                 }
             }
        }
        
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
             ret.add(minHeap.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = topKFrequent(words,2);
        System.out.println(ret);
    }
}